/*************************************************************************
	> File Name: 012.P1119_灾后重建.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created _time: 三  6/23 17:08:30 2021
 ************************************************************************/

#include <iostream>
#include <cstring>
using namespace std;

//now:到本次询问结束后，第几个点被修好
int n, m, q, arr[205][205], _time[205], now;

int main() {
    memset(arr, 0x3f, sizeof(arr));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> _time[i];
        arr[i][i] = 0;
    }

    for (int i = 0 ; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a++, b++;
        arr[a][b] = arr[b][a] = c;
    }
    cin >> q;
    while (q--) {
        int x, y, t;
        cin >> x >> y >> t;
        x++, y++;
        while (_time[now] <= t && now <= n) { //到t时间修好的点，该点为中转，跑floyd , 跑到第t天为止
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    arr[i][j] = min(arr[i][j], arr[i][now] + arr[now][j]);
                }
            }
            now++;
        }
        if (arr[x][y] == 0x3f3f3f3f || _time[x] > t || _time[y] > t) {
            cout << -1 << endl;
        } else {
            cout << arr[x][y] << endl;
        }
    }

    return 0;
}

